package com.example.lettcode._202411._20241126;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
594. 最长和谐子序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
给你一个整数数组 nums ，请你在所有可能的 子序列 中找到最长的和谐子序列的长度。
数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：
最长和谐子序列是 [3,2,2,2,3]。

示例 2：
输入：nums = [1,2,3,4]
输出：2
解释：
最长和谐子序列是 [1,2]，[2,3] 和 [3,4]，长度都为 2。

示例 3：
输入：nums = [1,1,1,1]
输出：0
解释：
不存在和谐子序列。

提示：
1 <= nums.length <= 2 * 104
-109 <= nums[i] <= 109
 */
public class _03_zui_chang_he_xie_zi_xu_lie {

    public static void main(String[] args) {
        int[] nums = {1,4,1,3,1,-14,1,-13};
        System.out.println(findLHS2(nums));
    }

    /*
        最终只要返回一个结果，所以，破坏数据的顺序性，来求结果
     */
    public static int findLHS(int[] nums) {
        Arrays.sort(nums);

        if (nums[nums.length-1] - nums[0] < 1) {
            return 0;
        }

        List<List<Integer>> list = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            List<Integer> tempList = new ArrayList<>();
            boolean flag = false;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] - nums[j] == 1) {
                    tempList.add(nums[j]);
                    flag = true;
                }

                if (nums[i] - nums[j] == 0) {
                    tempList.add(nums[j]);
                }
            }
            if (tempList.size() > 0 && flag ) {
                tempList.add(nums[i]);
                list.add(tempList);
            }
        }

        int max = Integer.MIN_VALUE;
        for (List<Integer> tempList : list) {
            max = Math.max(max, tempList.size());
        }
        return max;
    }


    public static int findLHS2(int[] nums) {
        Arrays.sort(nums);

        if (nums[nums.length-1] - nums[0] < 1) {
            return 0;
        }

        int start = 0, result = 0;
        for (int end = 1; end < nums.length; end++) {
            while (nums[end] - nums[start] > 1) {
                start++;
            }

            if (nums[end] - nums[start] == 1) {
                result = Math.max(result, end - start + 1);
            }
        }
        return result;
    }

}
